package gr.idocs.workshop.service;
/******************************************************************************
* File : ConcurrentMergeSort.java
* Author : http://java.macteki.com/
* Description :
*   Concurrent Merge Sort
* Tested with : JDK 1.6
******************************************************************************/
 
public class ConcurrentMergeSorter
{
 
  public static void printArray(int[] a)
  {
    String delim="";
    for (int i=0;i<a.length;i++)
    {
      System.out.print(delim+a[i]);
      delim=",";   // add delimiter after first element
    }
    System.out.println();
  }
 
 
  public static void mergeSort(String[] sortArray,int low,int high,String[] helper,int depth)
  throws Exception
  {
    int length=high-low+1;
    if (length<=1) return;   // a list with only 1 element is already sorted
    int mid=length/2;
 
    if (depth<=1)
    {
      // sort the left sub-list using a child thread
      SortingThread bThread=new SortingThread(sortArray,low,low+mid-1,helper,depth,"bThread ");
 
      // sort the right sub-list in the parent thread
      mergeSort(sortArray,low+mid,high,helper,depth+1);     
 
      bThread.join();                // parent-child synchronization
 
      merge(sortArray,low,high,helper);      // merge the sorted lists
    }
    else  // sequential merge sort
    {
      mergeSort(sortArray,low,low+mid-1,helper,depth+1);      // sort the left sub-list
      mergeSort(sortArray,low+mid,high,helper,depth+1);       // sort the right sub-list
      merge(sortArray,low,high,helper);      // merge the sorted lists
    }
  }
 
  public static void merge(String[] sortArray, int low,int high,String[] helper)
  {
    int mid=(high-low+1)/2;
    int ai=low,bi=low,ci=low+mid;
 
    while (ai<=high)
    {
      if (bi<=low+mid-1 && ci<=high)  // both lists contains element
      {
        helper[ai++]=(sortArray[bi].compareTo(sortArray[ci])<0)?sortArray[bi++]:sortArray[ci++];
      }   
      else if (bi<=low+mid-1)    // only list B contains element
      {
        while (ai<=high) helper[ai++]=sortArray[bi++];
      }
      else                    // only list C contains element
      {
        while (ai<=high) helper[ai++]=sortArray[ci++];     
      }
    }
 
    // copied back the helper to the input array
    for (int i=low;i<=high;i++)
    {
      sortArray[i]=helper[i];
    }
  }
 
 
//  public static void main(String[] args) throws Exception
//  {
//    int[] a={86,29,29,20,91,78,73,13,98,85,90,19,98,66,12,41,36,33,19,94,27,49,23,97,94};
// 
//    int[] helper=new int[a.length];
//    mergeSort(a,0,a.length-1,helper,0);   
//     
//    printArray(a);
//  }
}
// 
 
class SortingThread extends Thread
{
  static int threadCount;
  int threadID;
  String[] subArray=null;
  String[] helper=null;
  int depth=0;
  int low=0,high=0;
  String name="null";
 
  public SortingThread(String[] sortArray, int low,int high,String[] helper2,int depth, String name)
  {
	  
    this.subArray = sortArray;
    this.depth = depth;
    this.name = name;
    this.low=low;
    this.high=high;
    this.helper=helper2;
    this.threadID=threadCount++;
    this.start();  // start the thread immediately
  }
 
  // thread entry point
  public void run()
  {
    try
    {     

      ConcurrentMergeSorter.mergeSort(subArray,low,high,helper,depth+1);
      subArray=null;  helper=null;  // garbage collection friendly
    } catch (Exception e)
    {
      e.printStackTrace();
    }
  }
}